1. Field of the Invention (Technical Field)
The present invention relates to methods and apparatuses for load balancing on parallel computers, particularly massively parallel Multiple Instruction stream, Multiple Data stream (MIMD) computers.
2. Background Art
Distributed memory, massively parallel, MIMD technology has enabled the development of applications requiring computational resources previously unobtainable. Structural mechanics and fluid dynamics applications, for example, are often solved by finite difference or finite element methods requiring millions of degrees of freedom to accurately simulate physical phenomenon. On massively parallel computers, finite difference and finite element methods frequently result in distributed processor load imbalances. To overcome load imbalance, many massively parallel methods use static load balancing as a preprocessor to the finite element calculation. Fox et al, Solving Problems on Concurrent Processors, Volume 1 (Prentice Hall, Englewood, N.J., 1988); Hammond, Mapping Unstructured Grid Computations to Massively Parallel Computers (Ph.D. thesis, Rensselaer Polytechnic Institute, Dept. of Computer Science, Troy, N.Y., 1992); Hendrickson et al, "Multidimensional Spectral Load Balancing," Sandia National Laboratories Tech. Rep. SAND93-0074; and Kernighan et al, "An Efficient Heuristic Procedure for Partitioning Graphs," Bell Systems Tech. J. 29:291-307 (1970). Adaptive finite difference and finite element methods, which automatically refine or coarsen meshes and vary the order of accuracy of the numerical solution, offer greater robustness and computational efficiency than traditional methods by reducing the amount of computation required away from physical structures such as shock waves and boundary layers. Adaptive methods, however, complicate the load imbalance problem since the work per element is not uniform across the solution domain and changes as the computation proceeds. Therefore, dynamic load balancing is required to maintain global load balance.
The present invention is of a fine-grained, data driven, dynamic load balancing method referred to herein as "tiling". The invention is most useful for finite-element and finite-difference based applications. The method differs from those that use tasks as the unit of migration to achieve load balancing, such as Kale, "Comparing the Performance of Two Dynamic Load Distribution Methods," Int'l Conf. Of Parallel Processing (1988); Kao et al, "An Experimental Implementation of Migration Algorithms on the Intel Hypercube," Int'l J. of Supercomputer Applications Vol. 1, No. 2, 75-99 (1987); Leiss et al, "Distributed Load Balancing: Design and Performance Analysis," W. M. Keck Research Computation Lab. 5:205-70 (1989); Lin et al, "The Gradient Model Load Balancing Method," IEEE Trans. on Software Eng. (July 1987); Reddy, On Load Balancing (Ph.D. thesis, University of Houston, Dept. of Computer Science, 1989); Suen et al, "Efficient Task Migration Algorithm for Distributed Systems," IEEE Trans. on Parallel and Distributed Systems 488-99 (July 1992); and Schwederski et al, "A Model of Task Migration in Partitionable Parallel Processing Systems," IEEE Second Symposium On the Frontiers of Massively Parallel Computations 211-14 (1988). The present invention, to the contrary, uses a fine-grained, data-element based method for intra-application load balancing.